package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

import java.util.Arrays;

class GetEqualSubstringsWithinBudget {
    // 2022-08-24 12:45:42
    public static void main(String[] args) {
        Solution solution = new GetEqualSubstringsWithinBudget().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int equalSubstring(String s, String t, int maxCost) {
            int ans = 0;
            // 其实是求 和 < k 的最长子数组
            // 先构建数组
            int[] data = new int[s.length()];
            for (int i = 0; i < s.length(); i++) {
                data[i] = Math.abs(s.charAt(i) - t.charAt(i));
            }

            // 可以转化的最大长度
            // 通过测试案例确定 是连续子数组，那排序就不行了，只能滑动窗口
            int l = 0, r = 0;
            int sum = 0;
            while (r < data.length) {
                sum += data[r];
                while (sum > maxCost) {
                    sum -= data[l];
                    l++;
                }
                ans = Math.max(ans, r - l + 1);
                r++;
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}